Mathématique et cryptographie, une longue histoire ! - Olympiades 2020 Exercice 3

Le chiffre de César ou le chiffrement par décalage est une méthode de chiffrement très simple utilisée par Jules César dans ses correspondances secrètes. Le texte chiffré s’obtient en décalant chaque lettre d’un nombre fixe, appelé clé, dans l’ordre de l’alphabet.  Par exemple, avec une clé de  \(3\) vers la droite, \(A\)  est remplacé par \(D\) , \(B\)  devient \(E\) , et ainsi jusqu’à \(W\)  qui devient \(Z\) , puis \(X\) devient \(A\) , etc.

1. Coder le mot suivant avec la clé  \(3\) : \(\text{OLYMPIADES}\) .

2. Décoder le message suivant, chiffré par la méthode de César avec la clé \(9\) :  \(\text{JWWNN MNB VJCQNVJCRZDNB}\)

3. Décoder les trois parties du texte suivant, chiffré par la méthode de César, dont la clé est à deviner :

\(\begin{array}{|}\hline\textbf{Texte 1}\text{ : signé Alan Turing}\\\\\text{Chers amateurs de mathématiques,}\\\\\text{Depuis ma naissance en}\; \textit{qmppi riyj girx hsydi}\text{, la cryptographie me passionne. }\\\text{Le décodage est simpliste même si}\; \textit{Tcxleksvi ri ey wmbmiqi wmigpi ezerx Niwyw Glvmwx} \\\text{l'aurait trouvé brillant.}\qquad\\\\\textit{Eper Xyvmrk}\\\hline\end{array}\)

Soit  \(a\) et  \(b\) deux nombres entiers. Le cryptage affine consiste à remplacer chaque lettre de l’alphabet par un nombre, en commençant par  \(0\) pour la lettre \(A\) ,  \(1\) pour la lettre \(B\) ... jusqu’à  \(25\) pour la lettre \(Z\) , puis à remplacer le nombre initial  \(x\) par le nombre  \(y\) qui est le reste de la division euclidienne de  \(ax+b\) par \(26\) . Le couple  \((a\,;b)\) forme la clé du cryptage.

4. Avec la clé \((a\,;b)=(22\;;4)\) , détailler les calculs pour la lettre \(B\) .

5. Toujours avec la clé \((a\,;b)=(22\;;4)\) , coder les lettres  \(D\) et \(Q\) . Quel problème pratique engendre l’utilisation de cette clé ?

6. On change de clé : on prend \((a\,;b)=(9\;;4)\) . Dans l’algorithme ci-dessous,  \(m\;\%\;26\) désigne le reste de la division euclidienne de  \(m\) par \(26\) . Par exemple, \(28\; \%\; 26 = 2\) .
Cet algorithme permet de remplir le tableau de la question a.

\(\begin{array}{| l| } \hline\texttt{Entrer a} \\\texttt{Entrer b} \\ \texttt{x}\leftarrow\texttt{0} \\\texttt{Tant que x < 26} \\\qquad\quad\texttt{m}\leftarrow\texttt{ax + b}\\\qquad\quad\texttt{y}\leftarrow\texttt{m % 26} \\\qquad\quad\texttt{Afficher x, y}\\\qquad\quad\texttt{x}\leftarrow\texttt{x + 1}\\\texttt{Fin tant que}\\\hline \end{array}\)

    a. Recopier sur votre copie le tableau ci-dessous et le compléter pour tout l’alphabet.

\(\begin{array}{|l|}\hline\text{Lettre}&A&B&C&D&E&F&G&H&I&\dots\\\hline\text{Rang}\;x&0&1&2&3&4&5&\dots&\dots&\dots&\dots\\\hline m = ax + b&4&&&&&&&&&\\\hline \text{Rang}\;y&4&&&&&&&&&\\\hline\text{En crypté}&E&&&&&&&&&\\\hline\end{array}\)

    b. La clé (9 ; 4) résout-elle le problème rencontré à la question 5 ?

7. Décoder la partie du texte suivant, codé avec la clé \((a\;;b)=(9\;;4)\) .

\(\begin{array}{|}\hline\textbf{Texte 2}\\\text{Le mot algorithme tire son origine de }\textit{Ez-Qpeuebyviy ro or kojt wort scetbo lyrgtk,}\\\text{ père de l’algèbre. }\\\hline\end{array}\)

8. Proposer un algorithme de décodage. Toute trace de recherche sera prise en compte.

9. Quel est le principal défaut des deux systèmes de codage vus précédemment ?

On peut reprendre le chiffre de César de la partie 1 en changeant de clé pour chaque lettre. Ce chiffrement, le chiffrement de Vigenère, introduit la notion de clé, qui peut se présenter sous forme d’un mot ou d’une phrase. On choisit par exemple le mot clé \(\text{VIGENERE}\) , ce qui donnera :

• la clé \(21\)  (lettre \(V\) ) pour la  \(1^{re}\) lettre du message à coder ;
  
• la clé \(8\)  (lettre \(I\) ) pour la \(2^e\) lettre ;
  
• la clé \(6\)  (lettre \(G\) ) pour la \(3^e\)  lettre, etc. ;
  
• la clé \(4\)  (lettre \(E\) ) pour la  \(8^e\) lettre puis on recommence avec la clé  \(21\) (lettre \(V\) ) pour la  \(9^e\)  lettre, etc.
  

10. Décoder avec cette clé la date de naissance de Blaise Vigenère.

\(\begin{array}{|}\hline\textbf{Texte 3}\\\text{HQRPR GZRL KKRG ZZRBB-ZVBMJ} \\\hline\end{array}\)

11. Remplir la frise ci-dessous avec les noms des trois mathématiciens évoqués dans les textes précédents ainsi que leur année de naissance, parfois approximative.